package Sort;

/**
 * 排序(2)
 * 插入排序
 * time:2019.08.20
 * author:lipiao
 * 排序时间取决于初始数组的顺序，越接近有序越快，运行时间成线性，而此时选择排序成平方级别
 */
public class InsertionSort extends Template {

    //交换次数
    //static  int changeCount=0;

    //升序
    public static void sort(Comparable[] a) {
        int N = a.length;
        //System.out.println("排序过程:");

        //从下标为1开始遍历
        for (int i = 1; i < N; i++) {
            //System.out.println("插入"+a[i]);
            //遍历a[i]之前的元素 并插入到大于前一元素小于后一元素的位置
            //以此保证每次插入元素后下标为0到i的序列为升序
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                // a[j]<a[j-1] 小于前一元素则交换位置
                //System.out.println(a[j]+"<"+a[j-1]+",所以"+a[j]+"和"+a[j-1]+"交换位置");
                exch(a, j, j - 1);
                //记录交换次数
               // changeCount++;
//                 show(a);
            }
            //输出每次遍历后的结果
           // System.out.print("第"+i+"次遍历结果 ");
           // show(a);
            //System.out.println("=============");

        }
       // System.out.println("交换次数"+changeCount);
    }


//   无注释
//    public static void sort(Comparable[] a) {
//        int N = a.length;
//        for (int i = 1; i < N; i++) {
//            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
//                exch(a, j, j - 1);
//            }
//        }
//    }


    public static void main(String[] args) {
       // String[] a = {"c", "s", "d", "n", "x", "i", "n", "g", "w", "e", "i","s","h","e","l","l","s","o","r","t"};
        Comparable[] a=Template.getData(20);
        System.out.println("插入排序前");

        show(a);
        sort(a);

        assert isSorted(a);
        System.out.println("插入排序后");
        show(a);
    }

}
